#include<iostream>
#include<queue>
#include<string>
using namespace std;
#define M 2 //定义B+树每个节点最多放4个关键字

class Inter_Node;  //内部节点类
/***
 * 节点基类：所有节点（内部节点和叶子节点）的公共父类
 */
class Node
{
public:
    Node();  
    virtual ~Node();
    Node* GetBrother(int& flag);  //获取兄弟节点（用于删除时的借调和合并）
    Inter_Node* Parent; //故节点指针（指向内部节点）
    int key[M*2];  //关键字数组，节点最多放四个关键字，Max Degree = 5
    int count;  //记录当前节点存放的关键字数
    int isLeaf;  //表示节点是否为叶子节点（1：叶子节点；0：不是叶子节点）
public:
    void Print();
};

/**
 * 内部节点类：继承自Node，用于存储索引信息，指向子节点
 * 内部节点不直接存储数据，进存储关键字作为索引，引导查询
 */
class Inter_Node : public Node
{
public:
    Inter_Node();
    virtual ~Inter_Node();
    bool Insert(int value, Node* pNode); //插入关键字
    bool Delete(int value);  //删除关键字（及其对应的子节点）
    int Split(Inter_Node* pNode, int key); //节点满时分裂为当前节点和新节点
    bool Merge(Inter_Node* pNode); //与兄弟节点合并
    bool Slib(Inter_Node* pNode); //从兄弟节点借调关键字（平衡节点数量）
    Node* Child[M*2 + 1];
};

/***
 * 叶子节点类，继承Node，用于实际存储数据
 * 叶子节点构成双向链表，方便范围查询（前向和后向遍历）
 */
class Leaf_Node : public Node
{
public:
    Leaf_Node();
    virtual ~Leaf_Node();
    bool Insert(int value);
    bool Delete(int value);
    int Split(Leaf_Node* pNode);
    bool Merge(Leaf_Node* pNode);
    Leaf_Node* Pre_Node;
    Leaf_Node* Next_Node;
};

/***
 * B+树类：封装B+树的核心操作（插入、删除、查询、打印）
 */
class Bplus
{
public:
    Bplus();
    virtual ~Bplus();
    bool Search(int data, string &sPath);
    bool Insert(int data);
    bool Delete(int data);
    void Print();
protected:
    Leaf_Node* Find(int data); //查询数据所在的叶子节点
    bool Add_Node(Inter_Node* pNode, int key, Node* New_Node); //向内部节点添加子节点（处理分裂）
    bool Remove_Node(Inter_Node* pNode, int key);//从内部节点移除子节点
    Node* Root; //树的根节点
};

Node::Node()
{
    isLeaf = true; //默认初始化为叶子节点
    count = 0; //初始关键字数量为0
    Parent = NULL; //根节点指空
}
Node::~Node(){}
Node* Node::GetBrother(int& flag)
{//获取当前节点的兄弟节点
    if (NULL == Parent)//如果没有父节点则没有兄弟节点
        return NULL;
    Node* p = NULL;
    for (int i = 0; i <= Parent->count; i++)
    {//遍历寻找父节点的子节点，找到当前的位置
        if (Parent->Child[i] == this)
        {
            if (i == Parent->count)
            {//当前节点时父节点的最后一个子节点，兄弟节点是前一个
                p = Parent->Child[i - 1];
                flag = 1;
            }else//当前节点不是最后一个，则兄弟节点是后一个
            {
                p = Parent->Child[i + 1];
                flag = 2; //右兄弟
            }
        }
    }
    return p;
}

//打印节点中的关键字
void Node::Print()
{
    for (int i = 0; i < count; i++)
    {
        cout<< key[i] << " ";
        if (i >= count - 1)
            cout<< " | ";
    }
}

//内部节点构造函数，初始化内部节点特有属性
Inter_Node::Inter_Node()
{
    isLeaf = false;  //内部节点不是叶子节点
    for (int i = 0; i < M*2 + 1; i++)
        Child[i] = NULL; //初始化子节点指针为空，此时没有子节点
}
Inter_Node::~Inter_Node()
{
    for (int i = 0; i < M*2 + 1; i++)
        Child[i] = NULL;  //指针全部置空
}

//向内部节点插入关键字及其对应子节点
bool Inter_Node::Insert(int value, Node* New)
{//value:要插入的关键字 New:对应的子节点
    int i = 0;
    for (; (i < count) && (value > key[i]); i++){}//通过遍历查询插入位置
    for (int j = count; j > i; j--)  //移动关键字，腾出插入关键字所需位置
        key[j] = key[j - 1];
    for (int j = count + 1; j > i + 1; j--)//移动子节点指针，腾出位置
        Child[j] = Child[j - 1];
    key[i] = value;
    Child[i + 1] = New;
    New->Parent = this; //设置子节点的父节点为当前的节点
    count++; //关键字数+1
    return true;
}

//从内部节点删除关键字
bool Inter_Node::Delete(int k)
{
    int i = 0;
    for (; (k >= key[i]) && (i < count); i++){}//找到要删除的关键字
    for (int j = i - 1; j < count - 1; j++)//移动关键字，覆盖被删除的关键字
        key[j] = key[j + 1];
    //移动子节点指针，覆盖被删除关键字对应的子节点
    k = i;
    for (; k < count; k++)
    {
        Child[k] = Child[k + 1];
    }
    Child[k] = NULL;//将最后一个指针置空
    count--; //关键字数量-1
    return true;
}

//当内部节点关键字数量达到上限时，需要分裂成当前节点和新节点
int Inter_Node::Split(Inter_Node* p, int k)
{
    int i = 0, j = 0;
    //特殊情况，插入的关键字再中间位置，直接分裂成两个
    if ((k > this->key[M -1]) && (k < this->key[M]))
    {
        for (i = M; i < M*2; i++, j++)//复制后半部分关键字到新节点
            p->key[j] = this->key[i];
        //复制后半部分子节点到新节点，并更新父节点
        j = 1;
        for (i = M + 1; i <= M*2; i++, j++)
        {
            this->Child[i]->Parent = p;
            p->Child[j] = this->Child[i];
        }
        this->count = M; //当前节点保留前M个关键字
        p->count = M; //新节点保留后M个关键字
        return k; //提升插入的关键字到故节点
    }

    //常规情况，按中间位置分裂
    int pos = k < this->key[M - 1] ? (M - 1) : M;
    k = this->key[pos];
    j = 0;
    for (i = pos + 1; i < M*2; i++, j++)
        p->key[j] = this->key[i];
    j = 0;
    for (i = pos + 1; i <= M*2; i++, j++)
    {
        this->Child[i]->Parent = p;
        p->Child[j] = this->Child[i];
    }
    this->count = pos;  //当前节点保留前pos个关键字
    p->count = M*2 - pos - 1; //新节点保留剩余关键字
    return k;  //返回提升到父节点的关键字
}

//与兄弟内部节点合并
bool Inter_Node::Merge(Inter_Node* p)
{
    //插入兄弟节点的第一个子节点对应的关键字
    key[count] = p->Child[0]->key[0];
    count++;
    Child[count] = p->Child[0];  //合并子节点
    //复制兄弟节点的所有关键字和子节点
    for (int i = 0; i < p->count; i++)
    {
        key[count] = p->key[i];
        count++;
        Child[count] = p->Child[i + 1];
    }
    return true;
}

//平衡节点数量
bool Inter_Node::Slib(Inter_Node* p)
{//pNode：兄弟节点
    int i,j;
    if (p->key[0] < this->key[0]) //如果兄弟节点时左兄弟
    {
        //移动当前关键字和子节点腾出位置
        for (i = count; i > 0; i--)
            key[i] = key[i -1];
        for (j = count + 1; j > 0; j--)
            Child[j] = Child[j -1];
        key[0] = Child[0]->key[0]; //借调左兄弟的最后一个关键字和子节点
        Child[0] = p->Child[p->count];
    }else //如果兄弟节点是右兄弟
    {
        //借调右兄弟的第一个关键字和子节点
        key[count] = p->Child[0]->key[0];
        Child[count + 1] = p->Child[0];
        for (i = 1; i < p->count - 1; i++)//有兄弟移动关键字和子节点，填补空缺
            p->key[i - 1] = p->key[i];
        for (j = 0; j < p->count - 1; j++)
            p->Child[j] = p->Child[j + 1];
    }
    this->count++;
    p->count--;
    return true;
}

//叶子节点构造函数
Leaf_Node::Leaf_Node()
{
    isLeaf = true; //叶子节点标识
    Pre_Node = NULL; //前驱节点为空
    Next_Node = NULL; //后继节点为空
}
Leaf_Node::~Leaf_Node(){}

//向叶子节点中插入关键字
bool Leaf_Node::Insert(int value)
{
    int i = 0;
    for (; (value > key[i]) && ( i < count); i++){}
    for (int j = count; j > i; j--)
        key[j] = key[j - 1];
    key[i] = value;
    count++;
    return true;
}

//从叶子节点中删除关键字
bool Leaf_Node::Delete(int value)
{
    bool found = false;
    int i = 0;
    for (; i < count; i++)
    {
        if (value == key[i])
        {
            found = true;
            break;
        }
    }
    if (false == found)
        return false;
    int j = i;
    for (; j < count - 1; j++)
        key[j] = key[j + 1];
    key[j] = 0;
    count--;
    return true;
}

//叶子节点分裂
int Leaf_Node::Split(Leaf_Node* p)
{
    int j = 0;
    for (int i = M; i < M*2; i++, j++)
        p->key[j] = this->key[i];
    this->count = this->count - j;
    p->count = j;
    return p->key[0]; //返回新节点的第一个关键字（用于父节点索引）
}

//叶子节点合并
bool Leaf_Node::Merge(Leaf_Node* p)
{
    //检查合并后是否超过最大容量
    if (this->count + p->count > M*2)
        return false;
    //将兄弟节点的所有关键字插入当前节点
    for (int i = 0; i < p->count; i++)
        this->Insert(p->key[i]);
    return true;
}

Bplus::Bplus()
{
    Root = NULL;
}
Bplus::~Bplus(){}

//查询
bool Bplus::Search(int data, string &sPath)
{
    int i = 0;
    sPath = "查找路径为: ";
    Node* p = Root;
    if(NULL == p) //当树为空，直接返回错误
        return false;
    Inter_Node *q;
    while (NULL != p)  //从根节点开始遍历
    {
        if(p->isLeaf)
            break;
        //找到下一层节点的索引
        for (i = 0; (i < p->count) && (data >= p->key[i]); i++){}
        int k = i>0?i-1:i;  //记录对当前层经历过的关键字
        sPath += to_string(p->key[k]);
        sPath += "-->";
        q = (Inter_Node *)p;
        p = q->Child[i];
    }
    if (NULL == p)//遍历异常，未达到叶子节点
        return false;
    sPath += to_string(p->key[0]);
    bool found = false;
    for (i = 0; i < p->count; i++)
    {
        if (data == p->key[i])
            found = true;
    }
    if (found)
    {
        sPath += " ,查找成功.";
    }else
    {
        sPath += " ,查找失败, 不存在该数据.";
    }
    return found;
}

//查找数据所在的叶子节点
Leaf_Node* Bplus::Find(int data)
{
    int i = 0;
    Node* p = Root;
    Inter_Node* q;
    while (NULL != p)
    {
        if(p->isLeaf)
            break;
        for (i = 0; i < p->count; i++)
        {
            if (data < p->key[i])
                break;
        }
        q = (Inter_Node *)p;
        p = q->Child[i];
    }
    return (Leaf_Node*)p;
}

//向内部节点添加子节点
bool Bplus::Add_Node(Inter_Node* p, int k, Node* New_Node)
{
    if (NULL == p || p->isLeaf)//无效节点或非内部节点
        return false;
    if (p->count < M*2) //若当前节点未满，直接插入
        return p->Insert(k, New_Node);
    Inter_Node* Brother = new Inter_Node();//节点已经满了，需要分裂
    int NewKey = p->Split(Brother, k);
    //根据插入关键字的位置，决定插入当前节点还是新节点
    if (p->count < Brother->count) 
    {
        p->Insert(k, New_Node);
    }else if (p->count > Brother->count)
    {
        Brother->Insert(k, New_Node);
    }else
    {
        Brother->Child[0] = New_Node;
        New_Node->Parent = Brother;
    }
    //处理父节点
    Inter_Node* parent = (Inter_Node*)(p->Parent);
    if (NULL == parent)
    {
        parent = new Inter_Node();
        parent->Child[0] = p;
        parent->key[0] = NewKey;
        parent->Child[1] = Brother;
        p->Parent = parent;
        Brother->Parent = parent;
        parent->count = 1;
        Root = parent;
        return true;
    }
    //递归实现向上处理父节点
    return Add_Node(parent, NewKey, Brother);
}

//插入
bool Bplus::Insert(int data)
{
    string a;
    if (true == Search(data, a)) //数据存在，无法插入
        return false;
    Leaf_Node* Old_Node = Find(data); //找到目标叶子节点
    if (NULL == Old_Node)  //树为空的话，创建第一个节点（根节点，叶子节点）
    {
        Old_Node = new Leaf_Node;
        Root = Old_Node;
    }
    //叶子节点没有满，直接插入
    if (Old_Node->count < M*2)
        return Old_Node->Insert(data);
    //叶子节点已满，需要分裂
    Leaf_Node* New_Node = new Leaf_Node;
    int k = Old_Node->Split(New_Node); //创建新的叶子节点
    Leaf_Node* OldNext = Old_Node->Next_Node;//分裂当前的叶子节点，获取新的叶子节点的第一个关键字
    Old_Node->Next_Node = New_Node;
    New_Node->Next_Node = OldNext;
    New_Node->Pre_Node = Old_Node;
    if (NULL != OldNext)
       OldNext->Pre_Node = New_Node;
    //根据数据大小，插入到原本的节点或者新节点
    if (data < k)
    {
        Old_Node->Insert(data);
    }else
    {
        New_Node->Insert(data);
    }
    //处理父节点
    Inter_Node* parent = (Inter_Node*)(Old_Node->Parent);
    if (NULL == parent)//叶子节点是父节点，创建新的根节点
    {
        Inter_Node* New_Root = new Inter_Node;
        New_Root->Child[0] = Old_Node;
        New_Root->key[0] = k;
        New_Root->Child[1] = New_Node;
        Old_Node->Parent = New_Root;
        New_Node->Parent = New_Root;
        New_Root->count = 1;
        Root = New_Root;
        return true;
    }
    return Add_Node(parent, k, New_Node);
}

//从内部节点专用移除子节点
bool Bplus::Remove_Node(Inter_Node* p, int k)
{
    if (false == p->Delete(k))//删除关键字失败
    {
        return false;
    }
    Inter_Node* parent = (Inter_Node*)(p->Parent);
    if (NULL == parent)//如果当前节点是根节点
    {
        if (0 == p->count)//根节点关键字为0，更新根为子节点
        {
            Root = p->Child[0];
            delete p;
        }
        return true;
    }
    //若当前节点关键字数量满足最小要求，更新父节点的索引
    if (p->count >= M)
    {
        for (int i = 0; (i < parent->count) && (k >= parent->key[i]); i++)
        {
            if (parent->key[i] == k)
                parent->key[i] = p->key[0];//用当前节点第一个关键字更新父节点
        }
        return true;
    }
    //关键字数量不足，则向兄弟节点借
    int flag = 1;
    Inter_Node* Brother = (Inter_Node*)(p->GetBrother(flag));
    if (Brother->count > M)//如果兄弟节点有足够的节点借用
    {
        p->Slib(Brother);//借调关键字
        if (1 == flag) //借调左兄弟
        {
            for (int i = 0; i <= parent->count; i++)
            {
                if (parent->Child[i] == p && i > 0)
                    parent->key[i - 1] = p->key[0];
            }
        }else//借调右兄弟
        {
            for (int i = 0; i <= parent->count; i++)
            {
                if (parent->Child[i] == p && i > 0)
                    parent->key[i - 1] = p->key[0];
                if (parent->Child[i] == Brother && i > 0)
                    parent->key[i - 1] = Brother->key[0];
            }
        }
        return true;
    }
    //兄弟节点没有多余关键字，合并两个节点
    int NewKey = 0;
    if (1 == flag)//左兄弟合并
    {
        Brother->Merge(p);
        NewKey = p->key[0];
        delete p;
    }else//右兄弟合并
    {
        p->Merge(Brother);
        NewKey = Brother->key[0];
        delete Brother;
    }
    return Remove_Node(parent, NewKey);
}

//删除
bool Bplus::Delete(int data)
{
    Leaf_Node* Old_Node = Find(data);
    if (NULL == Old_Node)//叶子节点不存在
        return false;
    if (false == Old_Node->Delete(data))//没有找到相应的数据
        return false;
    Inter_Node* parent = (Inter_Node*)(Old_Node->Parent);
    if (NULL == parent) //叶子节点是根节点
    {
        if (0 == Old_Node->count)//叶子节点已经空，直接置空
        {
            delete Old_Node;
            Root = NULL;
        }
        return true;
    }
    //若叶子节点关键字书满足最小要求，同上
    if (Old_Node->count >= M)
    {
        for (int i = 0; (i < parent->count) && (data >= parent->key[i]); i++)
        {
            if (parent->key[i] == data)
                parent->key[i] = Old_Node->key[0];
        }
        return true;
    }
    int flag = 1;
    Leaf_Node* Brother = (Leaf_Node*)(Old_Node->GetBrother(flag));
    int NewData = 0;
    if (Brother->count > M)
    {
        if (1 == flag)
        {
            NewData = Brother->key[Brother->count - 1];
        }
        else{
            NewData = Brother->key[0];
        }
        Old_Node->Insert(NewData);
        Brother->Delete(NewData);
        if (1 == flag)
        {
            for (int i = 0; i <= parent->count; i++)
            {
                if (parent->Child[i] == Old_Node && i > 0)
                    parent->key[i - 1] = Old_Node->key[0];
            }
        }else
        {
            for (int i = 0; i <= parent->count; i++)
            {
                if (parent->Child[i] == Old_Node && i > 0)
                    parent->key[i - 1] = Old_Node->key[0];
                if (parent->Child[i] == Brother && i > 1)
                    parent->key[i - 1] = Brother->key[0];
            }
        }
        return true;
    }
    int NewKey = 0;
    if (1 == flag)
    {
        Brother->Merge(Old_Node);
        NewKey = Old_Node->key[0];
        Leaf_Node* OldNext = Old_Node->Next_Node;
        Brother->Next_Node = OldNext;
        if (NULL != OldNext)
            OldNext->Pre_Node = Brother;
        delete Old_Node;
    }else
    {
        Old_Node->Merge(Brother);
        NewKey = Brother->key[0];
        Leaf_Node* OldNext = Brother->Next_Node;
        Old_Node->Next_Node = OldNext;
        if (NULL != OldNext)
            OldNext->Pre_Node = Old_Node;
        delete Brother;
    }
    return Remove_Node(parent, NewKey);
}

void Bplus::Print()
{
    Node* p = Root;
    if (NULL == p) return;
    Inter_Node* a;
    int H = 0;
    queue<Node *> q;
    queue<int> h;
    q.push(p);
    h.push(1);
    while(!q.empty())
    {
        p = q.front();
        if(H != h.front())
        {
            cout<<endl;
            cout<< "第" << H << "层: "<<endl;
            H = h.front();
        }
        q.pop();
        h.pop();
        p->Print();
        if(NULL != p && !p->isLeaf)
        {
            a = (Inter_Node*)p;
            for(int i =0; i <= p->count; i++)
            {
                q.push(a->Child[i]);
                h.push(H + 1);
            }
        }
    }
}

//查找
void test2(Bplus* bplus, int data)
{
    string sPath;
    bplus->Search(data, sPath);
    cout<<sPath;
}
//插入
void test3(Bplus* bplus, int data)
{
    bool success = bplus->Insert(data);
    if (true == success)
    {
        cout<<"插入成功!"<<endl;
    }
    else
    {
        cout<<"插入失败!"<<endl;
    }
}
//删除
void test4(Bplus* bplus, int data)
{
    bool success = bplus->Delete(data);
    if (true == success)
    {
        cout<<"删除成功!"<<endl;
    }
    else
    {
        cout<<"删除失败!"<<endl;
    }
}
//打印
void test6(Bplus* bplus)
{
    bplus->Print();
}

int main()
{
    Bplus* bplus = new Bplus();
    int x = 1;
    int y = 0;
    while (0 != x)
    {
        cout<<"\n\n";
        cout<<"==========================\n";
        cout<<"=B+树演示程序，请选择相应功能=\n";
        cout<<"=   1--查找；     =\n";
        cout<<"=   2--插入；     =\n";
        cout<<"=   3--删除；     =\n";
        cout<<"=   4--打印；     =\n";
        cout<<"=其他任意键退出程序=\n";
        cout<<"==========================\n";
        cout<<"\n您的选择是：";
        cin>>x;
        switch (x)
        {
        case 1:
            cout<<"请输入要查找的数值：";
            cin>>y;
            test2(bplus, y);
            break;
        case 2:
            cout<<"请输入要插入的数值：";
            cin>>y;
            test3(bplus, y);
            break;
        case 3:
            cout<<"请输入要删除的数值：";
            cin>>y;
            test4(bplus, y);
            break;
        case 4:
            test6(bplus);
            break;
        default:
            delete bplus;
            return 0;
            break;
        }
    }
    return 0;
}
